import java.util.*;
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }

public class Test {
    /*
    题目 1：比较版本号
     */
    public int compare (String version1, String version2) {
        int v1 = 0;
        int v2 = 0;

        int len1 = version1.length();
        int len2 = version2.length();

        while(v1 < len1 || v1 < len2){
            long num1 = 0;
            //从下一个点前截取数字
            while(v1 < len1 && version1.charAt(v1) != '.'){
                num1 = num1 * 10 + (version1.charAt(v1) - '0');
                v1++;
            }
            //跳过点
            v1++;
            long num2 = 0;
            //从下一个点前截取数字
            while(v2 < len2 && version2.charAt(v2) != '.'){
                num2 = num2 * 10 + (version2.charAt(v2) - '0');
                v2++;
            }
            //跳过点
            v2++;
            //比较数字大小
            if(num1 > num2){
                return 1;
            }
            if(num1 < num2){
                return -1;
            }
        }
        //版本号相同
        return 0;
    }

    /*
    题目 2：二叉树的前序遍历
     */
    private void preorder(List<Integer> list,TreeNode root){
        if(root == null){
            return;
        }

        list.add(root.val);

        preorder(list, root.left);
        preorder(list, root.right);
    }

    public int[] preorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList();
        //递归前序遍历
        preorder(list,root);
        //返回结果
        int[] ret = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            ret[i] = list.get(i);
        }
        return ret;
    }

    /*
    题目 3：二叉树的中序遍历
     */
    private void inorder(List<Integer> list, TreeNode root){
        if(root == null){
            return ;
        }
        inorder(list, root.left);
        list.add(root.val);
        inorder(list, root.right);
    }

    public int[] inorderTraversal (TreeNode root) {
        //创建列表
        List<Integer> list = new LinkedList();
        //中序遍历
        inorder(list, root);
        //返回结果
        int[] ret = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            ret[i] = list.get(i);
        }
        return ret;
    }

    /*
    题目 4 ： 二叉树的后序遍历
     */
    public void postorder(List<Integer> list, TreeNode root){
        if(root == null){
            return;
        }
        postorder(list, root.left);
        postorder(list,root.right);
        list.add(root.val);
    }

    public int[] postorderTraversal (TreeNode root) {
        List<Integer> list = new LinkedList();
        postorder(list, root);
        int[] ret = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            ret[i] = list.get(i);
        }
        return ret;
    }

    /*
    题目 5：二叉树的最大深度
      */
    public int maxDepth (TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);

        int right = maxDepth(root.right);

        return Math.max(left , right) + 1;
    }

    /*
    题目 6：二叉树的层序遍历
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int size = queue.size();
        while ( !queue.isEmpty()) {
            ArrayList<Integer> temp = new ArrayList<>();
            while (size > 0) {
                TreeNode node = queue.poll();
                size--;
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                temp.add(node.val);
            }
            size = queue.size();
            lists.add(temp);
        }
        return lists;
    }

    /*
    题目 7： 对称的二叉树
     */
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot == null){
            return true;
        }
        return recursion(pRoot.left, pRoot.right);
    }

    private boolean recursion(TreeNode p1, TreeNode p2){
        if(p1 == null && p2 == null){
            return true;
            //短路机制！！
        }else if(p1 == null || p2 == null || p1.val != p2.val){
            return false;
        }

        return recursion(p1.left, p2.right) && recursion(p1.right, p2.left);
    }
}
